/*
更简洁的写法是：
从右往左找下降点 i
如果存在，找交换点 j 并交换
反转 i+1 到末尾
*/

//1.毛胚房
class Solution {
public:
    void nextPermutation(vector<int>& nums) {

        int i=0;
        int flag=0;
        int n = nums.size();
        for(int k=1;k<n;++k) {
            if(nums[k] <= nums[k-1]) {
                flag=1;
                continue;
            }
            else {
                flag=0;
                 break;
            }
               
        }
        if(flag)  {
            reverse(nums.begin(), nums.end());
            return;
        }

        for(int l=n-1;l>=1;--l) {
            if(nums[l] > nums[l-1]) {
                i = l-1;
                break;
            }
        }
        int j=0;
         for(int l=n-1;l>=1;--l) {
            if(nums[l] > nums[i]) {
                j = l;
                break;
            }
        }
        swap(nums[i], nums[j]);

        reverse(nums.begin()+ i + 1, nums.end());
    }
};
//2.精简一下
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int i = n - 2;

        // 1. 找到下降点
        while (i >= 0 && nums[i] >= nums[i+1]) {
            i--;
        }

        if (i >= 0) {
            // 2. 找到交换点
            int j = n - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums[i], nums[j]);
        }

        // 3. 反转后缀
        reverse(nums.begin() + i + 1, nums.end());
    }
};

